program OM_31;

{$APPTYPE CONSOLE}
 type pattern = record
        loc:integer;
        c:char;
      end;

 var pat:array[1..255]of pattern;
     freq:array['a'..'z']of integer;
     adaptedGs:array[0..255]of integer;
     QsBC:array['a'..'z']of integer;

  function MAX(a,b:integer):integer;
    begin
      if a>b then result := a
        else result := b;
    end;


  procedure OUTPUT(T,p:string;ofset:integer);
   begin
     writeln(T);
     while ofset >1 do begin
                        write(' ');
                        dec(ofset);
                       end;
     writeln(p);
   end;

 procedure preQsBC(p:string);
     var m,j:integer;
         i:char;
   begin
     m := length(p);
     for i:='a' to 'z' do
       QsBC[i]:=m + 1;
     for j:=1 to m do
       QsBC[p[j]]:=m - j + 1;
   end;

 function optimalPcmp(pat1,pat2:pattern):integer;
     var fx:integer;
   begin
     fx := freq[pat1.c] - freq[pat2.c];

     if (fx > 0) then optimalPcmp := fx
       else optimalPcmp := pat2.loc - pat1.loc;

   end;

 procedure qsort(m:integer);
     var i:integer;
         move:boolean;
         temp:pattern;
   begin

     repeat
       move:=false;
       for i:=1 to m - 1 do
         if (optimalPcmp(pat[i],pat[i+1])>0) then begin
                                                  temp := pat[i];
                                                  pat[i] := pat[i+1];
                                                  pat[i+1] := temp;
                                                  move := true;
                                                end;
     until (not move);


   end;

 procedure orderPatten(p:String);
     var i,m:integer;
   begin
     m := length(p);

     for i:=1 to m do
       begin
         pat[i].loc := i;
         pat[i].c := p[i];
       end;

     qsort(m);
   end;

 function matchShift(p:string;ploc,lshift:integer):integer;
     var i,j,m:integer;
   begin
     m := length(p);
     while (lshift < m) do
       begin
         i := ploc;
         while (i>=0) do
           begin
             j := pat[i].loc - lshift;
             dec(i);
             if (j<0) then Continue;
             if (pat[i+1].c <> p[j]) then Break;
           end;
         if (i<0) then Break;
         inc(lshift);
       end;
     matchShift := lshift;
   end;

 procedure pre_adaptedGs(p:string);
     var lshift,i,m,ploc:integer;
   begin
     m := length(p);

     lshift := 1 ;
     adaptedGs[0] := 1;
     for ploc:=1 to m do
       begin
         lshift := matchShift(p,ploc,lshift);
         adaptedGs[i] := lshift;
       end;

     for ploc := 0 to m do
       begin
         lshift := adaptedGs[ploc];
         while (lshift < m) do
           begin
             i := pat[ploc].loc - lshift;
             if (i <0)or(pat[ploc].c <>p[i]) then Break;
             inc(lshift);
             lshift := matchShift(p,ploc,lshift);
           end;
         adaptedGs[ploc] := lshift;
       end;
   end;

   procedure QM(T,p:string);
       var n,m,i,j:integer;
     begin
       orderPatten(p);
       preQsBC(p);
       pre_adaptedGs(p);

       n := length(T);
       m := length(p);

       j := 0;
       while (j <= n - m) do
         begin
           i := 1;
            while (i<=m)and(pat[i].c = T[j + pat[i].loc]) do inc(i);
            if i>m then OUTPUT(T,p,j);

            inc(j,MAX(adaptedGs[i],QsBC[p[j+m]]));
         end;
     end;

begin
  QM('gcatcgcagagagtatacagtacg','gcagagag');
  readln;
end.
